package basic.study.algorithms.struct;

/**
 * @author Kevin
 * @date 2020/2/12 14:54
 */
//从下标为0开始
public class Heap {
    private int[] a;// 数组，从下标1开始存储数据
    private int n;// 堆可以存储的最大数据个数
    private int count;// 堆中已经存储的数据个数

    public Heap(int capacity) {
        a = new int[capacity + 1];
        n = capacity;
        count = 0;
    }

    public void insert(int data) {
        if (count >= n) return;//堆满了
        ++count;
        a[count] = data;
        int i = count;
        while ((i-1)/2 > 0 && a[i] > a[(i-1)/2]) {// 自下往上堆化
            swap(a, i, (i-1)/2);// swap()函数作用：交换下标为i和i/2的两个元素
            i = (i-1) / 2;
        }
    }
    public void removeMax() {
        if (count == 0) return; //堆中没有数据
        a[0] = a[count];
        heapify(a, count, 0);
    }

    public void heapify(int[] a, int n, int i) {// 自上往下堆化
        while(true) {
            int maxPos = i;
            if (i * 2 + 1 <= n && a[i * 2 + 1] > a[i]) maxPos = i * 2 + 1;
            if (i * 2 + 2 <= n && a[i * 2 + 2] > a[maxPos]) maxPos = i * 2 + 2;
            if (maxPos == i) {
                break;
            }
            swap(a, i, maxPos);
            i = maxPos;
        }

    }

    public void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
